#pragma once
#include <queue>
#include <deque>

using namespace std;

class MaxQueue {
    queue<int> queVal;
    deque<int> queMax;
public:
    MaxQueue() {
    }

    int max_value() {
        if (queVal.size() == 0) return -1;
        return queMax.front();
    }

    void push_back(int value) {
        if (queMax.size() == 0) {
            queMax.push_back(value);
        }
        else {
            while (queMax.size() > 0) {
                if (value > queMax.back()) {
                    queMax.pop_back();
                }
                else {
                    break;
                }
            }
                
            queMax.push_back(value);
        }

        queVal.push(value);
    }

    int pop_front() {
        if (queVal.size() == 0)
            return -1;

        int val = queVal.front();
        if (val == queMax.front()) {
            queMax.pop_front();
        }

        queVal.pop();
        return val;
    }
};
